package org.laizili.solution.nowcodertop101.queue;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;

/**
 * <a href="https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=295&sfm=html&channel=nowcoder">BM45. 滑动窗口最大值</a>
 * <p>
 * tags: 滑动窗口; 双端队列;
 * </p>
 */
public class BM45 {
    private static class Solution {
        public ArrayList<Integer> maxInWindows(int[] num, int size) {
            Deque<Integer> queue = new ArrayDeque<>();
            int left = 0;
            int right = 0;
            ArrayList<Integer> res = new ArrayList<>();
            while (right < num.length) {
                if (right - left < size) {
                    int val = num[right];
                    while (!queue.isEmpty() && val > queue.peekLast()) {
                        queue.pollLast();
                    }
                    queue.offerLast(val);
                    right++;
                } else {
                    // len >= size
                    int leftVal = num[left];
                    int minVal = queue.peekFirst();
                    res.add(minVal);
                    if (leftVal == minVal) {
                        queue.pollFirst();
                    }
                    left++;
                }
            }
            res.add(queue.peekFirst());
            return res;
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution().maxInWindows(new int[]{2, 3, 1, 2}, 3));
    }
}
